package com.itheima.weiding;

public class LeetCodeLCR170 {
    //在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。
    // 请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
    //通过merge在归并排序的过程中比较左右两边的大小，同时计算数量

    public int reversePairs(int[] record) {
        if(record == null || record.length < 2){
            return 0;
        }
        return process(record,0,record.length-1);
    }

    //递归逻辑
    private int process(int[] args, int l, int r){
        if(l == r){
            return 0;
        }
        int mid = l + ((r - l) >>> 1);
        //左字树
        int left = process(args, l, mid);
        //右字树
        int right = process(args, mid + 1, r);
        //合并merge
        int con = merge(args, l, mid, r);

        return left + right + con;
    }


    //用于(由大到小排序)排序以及计算[交易逆序对]的数量
    private int merge(int[] args, int l, int m , int r){
        int help[] = new int[r - l + 1];
        int rl = l;
        int l2 = m + 1;
        int res = 0;
        int con = 0;

        while (l <= m && l2 <= r){
            res += args[l] > args[l2] ? (r - l2 + 1) : 0 ;
            help[con++]= args[l] > args[l2] ? args[l++] : args[l2++];
        }
        while(l2 <= r){
            help[con++] = args[l2++];
        }
        while(l <= m){
            help[con++] = args[l++];
        }
        for (int i = 0; i < help.length; i++) {
            args[rl + i] = help[i];
        }
        return res;
    }
}
